/*
 * Misjonärid ja inimsööjad
 * (c) Karl Puusepp, 2012
 * mudkip@ut.ee
 */

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.TreeSet;

import javax.swing.JFrame;
import javax.swing.JOptionPane;
import javax.swing.JScrollPane;
import javax.swing.JTextArea;

public class RCMain extends JFrame {
	private static final long serialVersionUID = 1L;
	
	int m, n, p, r; // rules to live by
	Set<RCStateTree> visited = new TreeSet<RCStateTree>();
	
	public class RCStateTree implements Comparable<RCStateTree> {
		
		int[] state; // state is vector of <m_left, n_left, boat_left>
		int depth;
		RCStateTree parent;
		List<RCStateTree> children;
		
		RCStateTree() {
			/* created as top tree*/
			parent = null;
			depth = 0;
			state = new int[]{m, n, 1};
			visited.add(this);
			generateChildren();
		}
		
		RCStateTree(int miss, int cann, int boat, RCStateTree from) {
			/* created as child */
			parent = from;
			depth = from.depth + 1;
			state = new int[] {miss, cann, boat};
		}
		
		void generateChildren() {
			
			if (this.state == new int[3])
				return;
			
			List<RCStateTree> localChildren = new ArrayList<RCStateTree>();
			int miss, cann, boat, lOrR;
			
			if (state[2] == 1) {
				// going left to right
				miss = state[0];
				cann = state[1];
				boat = 0;
				lOrR = -1;
			} else {
				// going right to left
				miss = m - state[0];
				cann = n - state[1];
				boat = 1;
				lOrR = 1;
			}
			// max in boat = p
			// min in boat = r
			
			for (int i = r; i <= Math.min(p, miss + cann); i++) {
				// i people on boat
				
				for (int j = 0; j <= Math.min(i, miss); j++) {
					// j missionaries to boat
					for (int k = 0; k <=Math.min(i-j, cann); k++) {
						// k cannibals to boat
						
						RCStateTree child = new RCStateTree(state[0]+lOrR*j, state[1]+lOrR*k, boat, this);
						boolean add = true;
						
						if (j+k <= p && j+k >= r && !(j>0 && !(j>=k)) /*A->B*/ && child.isLegalState()) {
							for (RCStateTree node : visited) {
								if (node.compareTo(child)==0) {
									if (child.depth < node.depth) add = true;
									else add = false;
								}
							}
							
						} else {
							add = false;
						}
						
						if (add) {
							localChildren.add(child);
							visited.add(child);
						}
					}
				}
			}
			
			this.children = localChildren;
			for (RCStateTree child : this.children) {
				child.generateChildren();
			}
			
		}
		
		RCStateTree bfs() {
			/*
			 * perform breadth-first search on solution tree
			 * return null if no solution found
			 */
			int[] solution = new int[] {0, 0, 0};
			
			Queue<RCStateTree> q = new ArrayDeque<RCStateTree>();
			q.add(this);
			while (!q.isEmpty()) {
				RCStateTree t = q.poll();
				if (Arrays.equals(t.state, solution))
					return t;
				for (RCStateTree child : t.children) {
					q.add(child);
				}
			}
			
			return null;
		}

		boolean isLegalState() {
			if ((state[0] != 0 && state[0] < state[1]) || (m - state[0] != 0 && m-state[0] < n - state[1]))
				return false;
			else
				return true;
		}
		
		@Override
		public int compareTo(RCStateTree o) {
			if (Arrays.equals(state, o.state))
				return 0;
			else if (state[0] + state[1] + state[2] > o.state[0] + o.state[1] + o.state[2]){
				return 1;
			} else {
				return -1;
			}
		}
		
		public String toString() {
			String stringValue = "Misjonäre: "+state[0]+" Kannibale: "+state[1]+" |";
			if (state[2] == 1)
				stringValue+=" \\_/-->>------ ";
			else
				stringValue+=" ------<<--\\_/ ";
			
			stringValue+="| "+"Misjonäre: "+(m-state[0])+" Kannibale: "+(n-state[1]);
			return stringValue;
		}
		
	}

	RCMain() {
		
		m = 1; // missionaries
		n = 1; // cannibals
		p = 2; // boat capacity
		r = 1; // min people in boat
		
		try {
			String[] userinput = JOptionPane.showInputDialog(null, 
					"Palun sisesta misjonäride arv, kannibalide arv, paadi mahtuvus ja sõudjate arv " +
					"nt: '3, 3, 2, 1'", "Misjonärid & inimsööjad", 
					JOptionPane.INFORMATION_MESSAGE).split("[;, ]+");
		
			m = Integer.parseInt(userinput[0]);
			n = Integer.parseInt(userinput[1]);
			p = Integer.parseInt(userinput[2]);
			r = Integer.parseInt(userinput[3]);
			
			RCStateTree tree = new RCStateTree();
			System.out.println("Tree created!");
			RCStateTree finalNode = tree.bfs();
			if (finalNode != null) {
				
				/* UI CREATION */
				
				this.setTitle("Misjonärid & inimsööjad");
				this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
				this.setSize(500,400);
				this.setLocationRelativeTo(null);
				this.setResizable(false);
				
				JTextArea textArea = new JTextArea(15, 80);
				textArea.setLineWrap(true);
				textArea.setEditable(false);
				
				JScrollPane scrollPane = new JScrollPane(textArea);
				scrollPane.setVerticalScrollBarPolicy(JScrollPane.VERTICAL_SCROLLBAR_AS_NEEDED);

				this.getContentPane().add(scrollPane);
				
				/* solution output */
				
				List<String> result = new ArrayList<String>();
				
				result.add(finalNode+"\n");
				int moves = finalNode.depth;
				while (finalNode.parent != null) {
					result.add(finalNode.parent + "\n");
					finalNode = finalNode.parent;
				}
				
				for (int i = result.size()-1; i >= 0; i--)
					textArea.append(result.get(i));
				
				textArea.append("\nLahendus leitud "+moves+ " käiguga.");
				
				this.setVisible(true);
				
				
			} else {
				JOptionPane.showMessageDialog(
						null, "Lahendit ei leitud!", "Trips-Traps-Trull", 
						JOptionPane.INFORMATION_MESSAGE, null);
			}
			
		} catch (NullPointerException e){
			System.exit(0);
		} catch (Exception e) {
			JOptionPane.showMessageDialog(
					null, "Viga sisendi esitamisel, palun proovi uuesti", "Trips-Traps-Trull", 
					JOptionPane.INFORMATION_MESSAGE, null);
			new RCMain();
		}
	}
	
	
	public static void main(String[] args) {
		new RCMain();
	}

}
